package third

/*
	输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回true，否则返回false。假设输入的数组的任意两个数字都互不相同。

	参考以下这颗二叉搜索树：

		 5
		/ \
	   2   6
	  / \
	 1   3
	示例 1：

	输入: [1,6,3,2,5]
	输出: false
	示例 2：

	输入: [1,3,2,6,5]
	输出: true

	提示：

	数组长度 <= 1000

	来源：力扣（LeetCode）
	链接：https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-hou-xu-bian-li-xu-lie-lcof
	著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/
func VerifyPostorder(postorder []int) bool {
	return verifyPostorder(postorder)
}

func verifyPostorder(postorder []int) bool {
	return _verifyPostorder(postorder, 0, len(postorder)-1)
}

func _verifyPostorder(postorder []int, l int, r int) bool {
	if l >= r {
		return true
	}
	if len(postorder) == 0 {
		return true
	}
	root := postorder[r]
	i := l
	for ; i <= r-1; i++ {
		if postorder[i] > root {
			break
		}
	}
	j := i
	for ; i <= r-1; i++ {
		if postorder[i] < root {
			return false
		}
	}
	return _verifyPostorder(postorder, l, j-1) && _verifyPostorder(postorder, j, r-1)
}
